RLC (run length coding) is appreciated as the most suitable technique for compressing binary image data. In the RLC method, series of repeated data are replaced with repeated numbers and pairs of data. When the size of the repeated data is great or the data are frequently repeated, the compression efficiency becomes high. Especially in the case of image data, RLC techniques are quite efficient since the data used for representing the same color are equal. The most important advantage of the RLC techniques is their simplicity in realizing the compression of data. Such RLC compression techniques are used not only for compression of multimedia data such as image data or sound data, but also for data transmission between systems.
The RLC techniques will now be described by the following example.
data string 1:                0×00, 0×01, 0×02, 0×03, 0×04, . . . , 0×fc, 0×fd, 0×fe, 0×ff        
data string 2:                0×20, 0×22, 0×28, 0×25, 0×21, . . . , 0×23, 0×21, 0×25, 0×27        
data string 3:                0×0a, 0×0a, 0×0a, 0×0a, 0×0a, . . . , 0×0a, 0×0a, 0×0a, 0×0a        
data string 4:                0×05, 0×11, 0×3f, 0×2e, 0×91, . . . , 0×0a, 0×ab, 0×7f, 0×19        
Data string 1 comprises 256 units of 8-bit data. Data string 2 comprises 256 units of 8-bit data. Data string 3 comprises 256 units of 8-bit data “0a”. Data string 4 comprises 256 units of 8-bit data that are irregularly arranged.
Under the RLC techniques, the data strings 1 through 4 are compressed as follows.
data string 1-1:                (0×00:0×00), (0×00:0×01), (0×00:0×02), (0×00:0×03), (0×00:0×04), . . . , (0×00:0×fc), (0×00:0×fd), (0×00:0×fe), (0×00:0×ff)        
data string 2-1:                (0×00:0×20), (0×00:0×22), (0×00:0×28), (0×00:0×25), (0×00:0×21), . . . , (0×00:0×23), (0×00:0×21), (0×00:0×25), (0×00:0×27)        
data string 3-1:                (0×ff:0×0a)        
data string 4-1:                (0×00:0×05), (0×00:0×11), (0×00:0×3f), (0×00:0×2e), (0×00:0×91), . . . , (0×00:0×0a), (0×00:0×ab), (0×00:0×7f), (0×00:0×19)        
The notation form of the RLC approach is (number of repeated data 5 elements:data value). For example, in data string 1, since the hexadecimal data “00” is repeated once, they are converted into (0×00:0×00). In data string 3, the hexadecimal data “0a” is repeated 256 times, thus being converted into (0×ff:0×0a).
According to the foregoing RLC technique, the 256-byte data comprised in the data string 1 are converted into the data of 256*(1+1) or 512 bytes, and the 256-byte data comprised in the data string 2 are converted into the data of 256*(1+1) or 512 bytes. The 256-byte data comprised in the data string 3 are converted into the data of 1*(1+1) or 2 bytes, and the 256-byte data comprised in the data string 4 are converted into the data of 256*(1+1) or 512 bytes.
In other words, the 768-byte data comprised in the data strings 1 through 4 are converted into the data of 512+512+2+512=1538 bytes by the RLC technique. The 1538 bytes of “compressed” data are 1.5 times as much as the original size (256+256+256+256=1024 bytes) of the data strings 1 through 4. As a result, when a series of adjacent data are frequently changed, the RLC compression technique may cause the data size to actually be increased.
To solve the foregoing problem of the conventional RLC techniques, a modified-RLC technique has been proposed. In the modified-RLC technique, the original data are converted into a form (command: data [, data, data, . . . , data]). The “command” is the number of a series of equal data or the number of a series of unequal data. Table 1 shows commands and respective meanings thereof.
TABLE 1CommandMeaning01EQ#202EQ#303EQ#404EQ#5...7eEQ#1277fEQ#12880NEQ#12881NEQ#127...FdNEQ#4FeNEQ#3FfNEQ#200NEQ#1
As shown in Table 1, the modified-RLC technique makes it possible to represent not only a series of equal data of 128 or less, but also a series of unequal data of 128 or less. By using the modified-RLC technique, the data strings 1 through 4 are compressed as follows.
data string 1-2                (0×80:0×01, 0×02, 0×03, . . . , 0×7d, 0×7e, 0×7f)        (0×80:0×80, 0×81, 0×82, . . . , 0×fd, 0×fe, 0×ff)        
data string 2-2                (0×80:0×20, 0×22, 0×28, . . . , 0×23, 0×21, 0×22)        (0×80:0×25, 0×21, 0×27, . . . , 0×21, 0×25, 0×27)        
data string 3-2                (0×7f:0×0a)        (0×7f:0×0a)        
data string 4-2                (0×80:0×05, 0×11, 0×3f, . . . , 0×5c, 0×00, 0×39)        (0×80:0×11, 0×81, 0×3f, . . . , 0×ab, 0×7f, 0×19)        
In the data string 1, since the 256 data bytes are different from each other, the data string 1-2 is divided into two groups, each of which consists of 128 data bytes according to the modified-RLC. Likewise, in the data string 2, since the 256 data bytes are different from each other, the data string 2-2 is divided into two groups, each of which consists of 128 data bytes.
When the data string 1 of 256 bytes is compressed by the modified-RLC, the data string 1-2 becomes (1+128)*2=258 bytes; when the data string 2 of 256 bytes is compressed by the modified-RLC, the data string 2-2 becomes (1+128)*2=258 bytes; when the data string 3 of 256 bytes is compressed by the modified-RLC, the data string 3-2 becomes (1+1)*2=4 bytes; and when the data string 4 of 256 bytes is compressed by the modified-RLC, the data string 4-2 becomes (1+128)*2=258 bytes. That is, the total 1024-byte data are compressed to 258+258+4+258=778 bytes, or ¾th of the original data size. However, in the event that a series of data are frequently changed like the data strings 1, 2, and 4, the compression efficiency still remains low.
Generally, series of multimedia-type data, particularly series of image data, tend to change progressively. For instance, in the case where a human face is photographed by a camera and converted into image data, most of the image data correspond to skin color. However, since the skin color changes slightly with varied direction of light, a value of the image data also changes. As mentioned above, when the adjacent data have slightly different values for indicating light and darkness, both the RLC and the modified-RLC have a significantly low compression rate. In addition, the size of the compressed data becomes greater.